package leecode

func pathSum3(root *TreeNode, targetSum int) int {
	var result int
	if root == nil {
		return result
	}
	result = backtracking3(root, targetSum)
	result += pathSum3(root.Left, targetSum)
	result += pathSum3(root.Right, targetSum)
	return result
}

func backtracking3(node *TreeNode, targetSum int) int {
	var result int
	if node == nil {
		return result
	}
	targetSum -= node.Val
	if targetSum == 0 {
		result++
	}
	result += backtracking3(node.Left, targetSum)
	result += backtracking3(node.Right, targetSum)
	targetSum += node.Val
	return result
}
